//判断子序列
class Solution {
public:
    bool isSubsequence(string s, string t) 
    {
        //dp[i][j] s的前i个和t的前j个组成的最大子序列
        int m=s.size();
        int n=t.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(s[i-1]==t[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else dp[i][j]=dp[i][j-1];
            }
        }
        return dp[m][n]==s.size();
    }
};
//不同的子序列
class Solution {
public:
    int numDistinct(string s, string t) 
    {
        //s是长的那个
        //dp[i][j] 以s[i-1]结尾的 包含t[j-1]在内的子序列个数
        //当s[i-1]==t[j-1]的时候 可以采用s[i-1]和t[j-1]进行匹配
        //也可以用之前的字符和t[j-1]进行匹配 
        //dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
        int m=s.size();
        int n=t.size();
        vector<vector<unsigned long long>>dp(m+1,vector<unsigned long long>(n+1,0));
        //初始化 s的前任意个字符 都可以出现一次空字符
        for(int i=0;i<=m;i++) dp[i][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(s[i-1]==t[j-1])
                {
                    //因为s的当前遍历的最后一个元素和t的最后一个相同
                    //无需考虑 所以用当前字符就是dp[i-1][j-1]
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                }
                else
                {
                    //只能用之前的字符去匹配 t的最后一个字符
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[m][n];
    }
};
//两个字符串的删除操作
class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        //dp[i][j] 使word1[i-1]结尾的字符串和以word2[j-1]结尾的字符串相同的最小步数
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
        for(int i=0;i<=m;i++) dp[i][0]=i;
        for(int j=0;j<=n;j++) dp[0][j]=j;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(word1[i-1]==word2[j-1])
                {
                    //相同了 这一步不用删除 和之前需要的次数一样
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
                    //看看从哪里删除过来次数少+当前需要删除一次
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
};
//编辑距离
class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        //dp[i][j] 以word1[i-1]结尾的字符串变成以word2[j-1]结尾的字符串的最少操作数
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
        for(int i=0;i<=m;i++) dp[i][0]=i;
        for(int j=0;j<=n;j++) dp[0][j]=j;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(word1[i-1]==word2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
};
//回文子串
class Solution {
public:
    int countSubstrings(string s) 
    {
        //dp[i][j] 从下标i到下标j是不是回文子串
        //if(s[i]==s[j]) 取决于dp[i+1][j-1]
        //所以i要从大到小进行遍历 而j要从小到大进行遍历
        //但 i<=j
        int n=s.size();
        vector<vector<bool>>dp(n,vector<bool>(n,false));
        int res=0;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(j-i<=1)
                    {
                        dp[i][j]=true;
                        res++;
                    }
                    else
                    {
                        dp[i][j]=dp[i+1][j-1];
                        if(dp[i][j]) res++;
                    }
                }
            }
        }
        return res;
    }
};
//最长回文子序列
class Solution {
public:
    int longestPalindromeSubseq(string s) 
    {
        //dp[i][j] 从下标i到下标j的最长回文子序列
        //因为dp[i][j]取决于dp[i+1][j-1]
        //所以i从大到小遍历 j从小到大遍历 且i<=j
        int n=s.size();
        vector<vector<int>>dp(n,vector<int>(n,0));
        for(int i=0;i<n;i++) dp[i][i]=1;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    //因为严格控制 i<j  不存在dp[i][i]经计算为2
                    //即 i==j时 是不符合下面的判断逻辑的
                    //i>j时的dp在初始化时是0
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                else
                {
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};